#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

// 用于记忆化的结构体，包含字符串位置和当前余数
struct State {
    int pos;
    int remainder;
    bool operator==(const State& other) const {
        return pos == other.pos && remainder == other.remainder;
    }
};

// 哈希函数，用于unordered_map中State类型的键
namespace std {
    template<>
    struct hash<State> {
        size_t operator()(const State& s) const {
            return hash<int>()(s.pos) ^ (hash<int>()(s.remainder) << 1);
        }
    };
}

// 记忆化搜索函数
int dfs(const string& s, int p, unordered_map<State, int>& memo, int pos = 0, int remainder = 0) {
    // 如果当前位置到达了字符串末尾，则检查余数是否为0
    if (pos == s.size()) {
        return remainder == 0 ? 1 : 0;
    }

    State currentState = {pos, remainder};
    // 如果已经计算过这个状态，直接返回结果
    if (memo.find(currentState) != memo.end()) {
        return memo[currentState];
    }

    int count = 0;
    // 尝试将当前位置的字符加入当前子串，并更新余数
    for (int i = pos; i < s.size(); ++i) {
        int newRemainder = (remainder * 10 + (s[i] - '0')) % p;
        count += dfs(s, p, memo, i + 1, newRemainder);
    }

    // 记录并返回结果
    return memo[currentState] = count;
}

// 主函数，用于初始化并调用递归函数
int countDivisibleSubstrings(const string& s, int p) {
    unordered_map<State, int> memo;
    return dfs(s, p, memo);
}

int main() {
    string s = "102"; // 示例输入字符串
    int p = 2; // 示例输入整数

    cout << "Number of divisible substrings: " << countDivisibleSubstrings(s, p) << endl;
    return 0;
}